package com.company.OfferGuide;

public class 背包01 {

    public static void main(String[] args) {
        System.out.println(knapsack());
    }

    static int N = 6;
    static int W = 21;

    static int[][] B = new int[N][W];
    static int[] w = new int[]{0,2,3,4,5,9};
    static int[] v = new int[]{0,3,4,5,8,10};

    static int knapsack(){
        int k,C;
        for (k = 1; k < N; k++) {
            for (C = 1; C <  W ;C ++) {
                if (w[k] > C) {
                    B[k][C] = B[k -1][C];
                } else {
                    int value01 = B[k - 1][C - w[k]] + v[k];
                    int value02 = B[k - 1][C];
                    B[k][C] = Math.max(value01,value02);
                }
            }
        }

        return B[N-1][W-1];

    }

}
